#include "main/utils.h"
using namespace std;

int singleNum(const vector<int>& vec) {
  if (vec.size() % 2 == 0) {
    cout << "invalid input." << endl;
    return -1;
  }
  int begin = 0;
  int end = vec.size() / 2;
  while (begin <= end) {
    int mid = (begin + end) / 2;
    int idx = 2 * mid;
    if (idx < vec.size() - 1 && vec[idx] != vec[idx + 1]) {
      if (mid == 0 || vec[idx - 2] == vec[idx - 1]) {
        return vec[idx];
      }
      end = mid - 1;
    } else {
      begin = mid + 1;
    }
  }
  return vec[vec.size() - 1];
}

int main() {
  vector<int> vec = {1, 1, 2, 2, 3, 4, 4, 5, 5};
  cout << singleNum(vec) << endl;

  vec = {1, 2, 2, 3, 3, 4, 4, 5, 5};
  cout << singleNum(vec) << endl;

  vec = {2, 2, 3, 3, 4, 4, 5, 5, 6};
  cout << singleNum(vec) << endl;

  vec.clear();
  cout << singleNum(vec) << endl;

  return 0;
}
